package com.demo.java.OD501_550.OD549;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【两个字符串间的最短路径问题(C卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146530934
 */
public class OdMain {
    public static int result = Integer.MAX_VALUE; // 存储最短路径

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] input_strs = in.nextLine().split(" ");
        char[] str1 = input_strs[0].toCharArray();  // 字符串 A
        char[] str2 = input_strs[1].toCharArray();  // 字符串 B
        int n = str1.length;  // 字符串 A 的长度
        int m = str2.length;  // 字符串 B 的长度

        // 记录是否已访问该位置
        int[][] visited = new int[n + 2][m + 2];
        for (int i = 0; i <= n + 1; i++) {
            for (int j = 0; j <= m + 1; j++) {
                visited[i][j] = 0;
            }
        }

        // 使用队列进行 BFS
        LinkedList<int[]> lst = new LinkedList<>();
        lst.offer(new int[]{-1, -1, 0});  // 初始状态，-1表示起始位置，0表示当前操作次数

        while (true) {
            if (lst.size() <= 0) {
                System.out.println(result);  // 输出最终的最短路径
                break;
            } else {
                int[] current = lst.poll();  // 取出当前节点

                // 如果到达了目标行 n
                if (current[0] + 1 == n) {
                    if (current[2] - current[1] + m - 1 < result) {
                        result = current[2] - current[1] + m - 1;  // 更新最短路径
                    }
                    continue;
                }
                // 如果到达了目标列 m
                if (current[1] + 1 == m) {
                    if (current[2] - current[0] + n - 1 < result) {
                        result = current[2] - current[0] + n - 1;  // 更新最短路径
                    }
                    continue;
                }

                // 如果当前字符匹配
                if (str1[current[0] + 1] == str2[current[1] + 1]) {
                    if (visited[current[0] + 2][current[1] + 2] == 0) {
                        visited[current[0] + 2][current[1] + 2] = 1;
                        lst.offer(new int[]{current[0] + 1, current[1] + 1, current[2] + 1});  // 向下和向右移动
                    }
                } else {
                    // 字符不匹配时，分别考虑向下和向右
                    if (visited[current[0] + 2][current[1] + 1] == 0) {
                        visited[current[0] + 2][current[1] + 1] = 1;
                        lst.offer(new int[]{current[0] + 1, current[1], current[2] + 1});  // 向下
                    }
                    if (visited[current[0] + 1][current[1] + 2] == 0) {
                        visited[current[0] + 1][current[1] + 2] = 1;
                        lst.offer(new int[]{current[0], current[1] + 1, current[2] + 1});  // 向右
                    }
                }
            }
        }
    }
}